package leetcode101.search_problem.bfs;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code7
 * @Description 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 一个数独的解法需遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * 空白格用 '.' 表示。
 * <p>
 * 一个数独。
 * 答案被标成红色。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-08 9:07
 */
public class Code7 {
    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solveSudoku(board);
    }

    public static boolean solved;
    public static int[][] row, col, block;

    public static void solveSudoku(char[][] board) {
        row = new int[9][9];
        col = new int[9][9];
        block = new int[9][9];
        solved = false;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != '.') {
                    int num = Character.getNumericValue(board[i][j]);
                    row[i][num - 1] = 1;
                    col[j][num - 1] = 1;
                    block[(i / 3) * 3 + (j / 3)][num - 1] = 1;
                }
            }
        }
        dfs(board, 0, 0);
        System.out.println("lxx");
    }

    public static void dfs(char[][] board, int i, int j) {
        if (solved) {
            return;
        }
        if (i == board.length) {
            solved = true;
            return;
        }
        if (board[i][j] != '.') {
            if (j < 8) {
                dfs(board, i, j + 1);
            } else {
                dfs (board, i + 1, 0);
            }
        } else {
            for (int k = 1; k <= 9; k++) {
                if (isValid(i, j, k)) {
                    board[i][j] = String.valueOf(k).charAt(0);
                    row[i][k - 1] = 1;
                    col[j][k - 1] = 1;
                    block[(i / 3) * 3 + (j / 3)][k - 1] = 1;
                    if (j < 8) {
                        dfs(board, i, j + 1);
                    } else {
                        dfs(board, i + 1, 0);
                    }
                    if (!solved) {
                        board[i][j] = '.';
                        row[i][k - 1] = 0;
                        col[j][k - 1] = 0;
                        block[(i / 3) * 3 + (j / 3)][k - 1] = 0;
                    }
                }
            }
        }
    }

    public static boolean isValid(int i, int j, int k) {
        if (row[i][k - 1] == 1) {
            return false;
        }
        if (col[j][k - 1] == 1) {
            return false;
        }
        if (block[(i / 3) * 3 + (j / 3)][k - 1] == 1) {
            return false;
        }
        return true;
    }

}
/*
1. 主要思路就是回溯，把所有情况进行尝试
2. 当填写第i行第j列的元素时，要知道其对应的行、列、块中 数字的使用情况，从而进行数组的第一步筛选。
因为矩阵大小固定9 * 9 所以新建row[9][9], col[9][9], block[9][9]来对数组中的数字进行存储方便筛选
这三个矩阵，第一维度表示所在的行、列、块索引，第二维度表示相应的数字，值为1代表已存在
如：row[1][2] 表示第二行的数字3已经被使用了。
3. 如何计算第i行第j列块所在的索引呢
块索引 = (i / 3) * 3 + (j / 3)
 */